COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP
C00004 00003	2Introductory material*
C00010 00004	2An example: the Monkey and Bananas Problem*
C00018 ENDMK
C⊗;
.DEVICE XGP
.!XGPCOMMANDS←"/TMAR=30/PMAR=2130/BMAR=40"

.FONT 1 "BASL30"
.FONT 2 "BDR40"
.FONT 4  "BASI30"
.FONT 5 "BASB30"
.FONT 6 "NGR25"
.FONT 7  "NGR20"
.FONT 8 "GRFX35"
.TURN ON "↑↓_π{"
.TURN ON "⊗" FOR "%"
.PAGE FRAME 50 HIGH 84 WIDE
.AREA TEXT LINES 4 TO 48
.AREA HEADING LINES 1 TO 3
.AREA FOOTING LINE 50
.!XGPLFTMAR←200
.SPACING 55 MILLS
.PREFACE 160 MILLS
.NOFILL
.PREFACE 45 MILLS
.FILL
.COUNT PAGE PRINTING "1"
.PAGE←0
.NEXT PAGE
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO GRAP ⊂ BEGIN GROUP SELECT 8 TURN OFF "↑↓←→" NOFILL ⊃
.MACRO E ⊂ APART END ⊃
.TABBREAK
.EVERY FOOTING(⊗7{DATE},,page {PAGE})
.TURN OFF "{→←}"
.PAGE←0
.NEXT PAGE
.ONCE CENTER
⊗2Introductory material⊗*

Consider a problem which is cast in the state-variable/operator formulation
discussed in [Nilsson]. The ⊗4goal⊗* is simply one (or more) states, as is
the ⊗4initial situation⊗*. From any given state S, several operators may be
applicable. Whichever one is applied, it transforms the current state into
another one. This paper considers the following task: examine
the original set R of operators, and preprocess it into a new set D of deterministic
operators
(from any given state at most one operator from D is applicable) yet any
state which could become the goal state by some sequence of operators in R, 
now becomes the goal state by a sequence of operators from D.
In other words, we still want to be able to solve any solvable node, yet
at each node we want there to be a unique operator which is applicable. Thus
the actual solution process will not involve searching.  Of course searching
cannot magically disappear: the procedure which preprocesses R will have to
involve either searching or unlimited parallel processing. 

Each operator consists of a predicate, whose conjuncts are called preconditions,
and a set of assignments.   <X :  P(X)?   T(X)> is an abbreviated way of specifying
an operator whose predicate P examines variables from X={x↓i} and, if it is
satisfied, carries out all the transformations {x↓i ← T(x↓i)}.
Let INITIAL be the initial state, A↓o the final goal state, R the set of operators
we are given, D the set of deterministic operators we must create.

Our procedure is not very complicated. We shall create several alternate sets D↓j.
Whenever one of them contains an operator which can be applied to INITIAL, 
we may stop and use that set as our D.  Our procedure will guarantee that 
only one operator will apply to each succeeding state, until finally we arrive in
state A↓o and stay there.

One operator which surely can go into D is the HALT operator, which we shall call
d↓o, whose preconditions are all of A↓o, and which performs no transformations
at all:  when we are in the goal state, we stay there.
This gives us an initial set D↓o = {d↓o}.  If INITIAL falls within the domain
of applicability of one of these operators, we are done (if we start out already
in the goal state, we never leave it).

To consider less trivial cases, we continue our procedure.  At any stage we shall
have a large collection ⊗2C⊗* of possible sets D↓j of operators d↓j↓k.
Pick any such D↓j (or, alternately, work on them all in parallel).
Pick one of its operators d↓j↓k. Now look at all the operators in R. Can any of
them ever help to acheive the preconditions which d↓j↓k demands in order to
work?  If so, what specializations, what constraints can be put upon the
helping operator?  For every such more deterministic operator r, add it to
D↓j, making a new, separate  possible set for D, a new element of ⊗2C⊗*. 
Throw it away immediately if
it is no longer deterministic: if r can be applied in any situation that any
other operator in D↓j can be applied in. Notice the fantastic rate of growth
of ⊗2C⊗*.   If we ever consider a D↓j which has no operators which can be
helped, and none which apply to INITIAL,
then we may throw that D↓j away also.  This process continues until
some d↓i↓j in some D↓i can be applied to INITIAL. When this happens, we know
that d↓i↓j is just helping to establish the preconditions for another operator
which will establish the preconditions.... which will establish the preconditions
for d↓o which means that we are in state A↓o.
.SKIP TO COLUMN 1
.ONCE CENTER
⊗2An example: the Monkey and Bananas Problem⊗*

To illustrate the basic idea, we shall work through a simplified version of the
infamous Monkey and Bananas Problem. 

A ⊗4state⊗* S has only two components, (m,b), indicating the position of the
monkey and the position of the box. The only distinguished positions are
BA (the position of the bananas), m↓i (the initial position of the monkey),
and b↓i (the initial position of the box).

There are only two operators, Go and Push. 
Go(x,y) will transport the monkey from  x to y. More formally,
Go(x,y) applies to a state
whose monkey-position is x, and performs the assignment x:=y.
The precondition is that  the monkey 
is not already at y, that is, x⊗8≠⊗*y.
Push(x,b,y) lets the monkey push the box to y.  A state (x,b) is transformed
into (y,y). The precondition is that the monky be at the box, x=b, and that
this position is different from y, x⊗8≠⊗*y.

With this statement of the problem, a complete graph of the situation can be
grown, but it will of necessity be nondeterministic:

.GRAP
			(mi,bi)

           go(mi,bi)   	   	   go(mi,y) with y⊗8≠⊗*bi



		          go(y,bi)
	      (bi,bi) =================	(y,bi)         loop via go(y,y') with y'⊗8≠⊗*bi
		      go(bi,y) with y⊗8≠⊗*bi

push(bi,bi,BA)	         push(bi,bi,z) with z⊗8≠⊗*BA,z⊗8≠⊗*bi


        (BA,BA)←ααααααααα(z,z)
            push(bi,bi,BA)
		              	    go(z)
			  go(y)
				 
			  	   (y,z)	       loop via go(y,y') with y'⊗8≠⊗*z
.END

The first step in  our preprocessing is to admit the HALT operator, whose
precondition is the goal state, (BA,BA), and which makes no change in that state.
We shall also refer to this operator as d↓o.
.GRAP


(BA,BA)		  HALT


.END

The next step is to examine all the  operators in R={go, push}, 
to see how they might
help acheive the preconditions of some operator in D↓o={d↓o}.  go(x,BA) can bring
about the goal, provided that the box is already at BA but that the monkey isn't.
Notice how crucial it is that go(x,x) be illegal: otherwise our set D would already
be nondeterministic (from (BA,BA) we could apply both HALT and go(BA,BA)).
We thus have the following graph so far:
.GRAP


(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x⊗8≠⊗*BA
		go(x,BA)


      HALT
.END

The push operator can acheive the preconditions of HALT iff the current state is of
the form (z,z), where z⊗8≠⊗*BA. Again, this last condition is crucial to keeping
D deterministic. Our new tentative D thus contains three operators now:
.BEGIN NOFILL
d↓o = HALT; precondition is (BA,BA), transformation is null.
d↓1 = go(BA); precondition is (x⊗8≠⊗*BA,BA), transformation is x:=BA.
d↓2 = push(x,x,BA); precondition is (x⊗8≠⊗*BA,x), transformation is x:=BA.
.END

.GRAP

			(x,x) with x⊗8≠⊗*BA


    	            push(x,x,BA)


(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x⊗8≠⊗*BA
		go(x,BA)


      HALT
.END

There is no other way that either push or go can help acheive the preconditions
that HALT demands.  We now turn to ways to help operators in D↓1={d↓o,d↓1,d↓2}.
Nothing can help d↓o or d↓1. For d↓2, however, we find that go(z,x) ⊗4can⊗*
bring about (x,x), but only when the box was originally at x.
This unfortunately conflicts with d↓1, in the situation (x,BA). So we stipulate
that our new specialized go operator must only apply when the box is ⊗4not⊗* at BA.
A smart algorithm would recognize that the two operators
d↓1 and our new d↓3 can be combined, since from (x,BA) we go to (BA,BA), while
from (z,x) we go to (x,x) when x⊗8≠⊗*BA.  These both could become a single go operator,
go(z,x) whose only precondition is that z does not already equal x.
The algorithm we later present does not do such optimizations, so our picture
must remain cluttered:

.GRAP

(z,x) with z⊗8≠⊗*x, x⊗8≠⊗*BA


		    go(z,x)


			(x,x) with x⊗8≠⊗*BA


    	            push(x,x,BA)


(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x⊗8≠⊗*BA
		go(x,BA)


      HALT
.END

We finally arrive at a set D↓2={d↓o,d↓1,d↓2,d↓3} which contains 
operators which can apply in any conceivable state of the world, yet
no two of which ever want to apply to the same same.
Incidentally, there is no way either operator in R can be
further specialized to help acheive the preconditions of any operator in D↓2.
Thus our procedure terminates here for two reasons (success and exhaustion).
Notice how much more direct the above graph is; not only is every original
initial state still solvable, but the solution path is in no case any longer
than the ideal path using operators from R.